Excuse Me! or The Courteous Theatregoers' Problem

摘要

Consider a theatre consisting of $m$ rows each containing $n$ seats.Theatregoers enter the theatre along aisles and pick a row which they enteralong one of its two entrances so as to occupy a seat. Assume they select theirseats uniformly and independently at random among the empty ones. A row ofseats is narrow and an occupant who is already occupying a seat is blockingpassage to new incoming theatregoers. As a consequence, occupying a specificseat depends on the courtesy of theatregoers and their willingness to get up soas to create free space that will allow passage to others. Thus, courtesyfacilitates and may well increase the overall seat occupancy of the theatre. Wesay a theatregoer is courteous if (s)he will get up to let others pass.Otherwise, the theatregoer is selfish. A set of theatregoers is $p$-courteousif each theatregoer in the set is courteous with probability $p$, randomly andindependently. It is assumed that the behaviour of a theatregoer does notchange during the occupancy of the row. In this paper, we are interested in the following question: what is theexpected number of occupied seats as a function of the total number of seats ina theatre, $n$, and the probability that a theatregoer is courteous, $p$? Westudy and analyze interesting variants of this problem reflecting behaviour ofthe theatregoers as entirely selfish, and $p$-courteous for a row of seats withone or two entrances and as a consequence for a theatre with $m$ rows of seatswith multiple aisles. We also consider the case where seats in a row are chosenaccording to the geometric distribution and the Zipf distibrution (as opposedto the uniform distribution) and provide bounds on the occupancy of a row (andthus the theatre) in each case.